package com.breeze.leetcode;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/min-stack/
 * 155. 最小栈
 * 设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
 * <p>
 * push(x) —— 将元素 x 推入栈中。
 * pop() —— 删除栈顶的元素。
 * top() —— 获取栈顶元素。
 * getMin() —— 检索栈中的最小元素。
 */

/**
 * 方法一：有序列表维护最小值，采用二分发维护，故时间复杂度O(logn)
 */
public class LeetCode155 {
    private List<Integer> stack;
    private List<Integer> sortList;

    public LeetCode155() {
        stack = new LinkedList<>();
        sortList = new ArrayList<>();
    }

    public void push(int x) {
        stack.add(x);
        //  Collections.sort(sortList);
        // 采用二分法查找下标，插入提高速度
        int index = findIndex(x);
        sortList.add(index, x);
    }

    private int findIndex(int target) {
        if (sortList.size() == 0) {
            return 0;
        }
        int left = 0;
        int right = sortList.size() - 1;
        while (left < right) {
            int mid = (left + right) / 2;
            if (sortList.get(mid) == target) {
                return mid;
            } else if (sortList.get(mid) < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        // left == right 的情况
        return target <= sortList.get(left) ? left : left + 1;
    }

    public void pop() {
        int value = stack.remove(stack.size() - 1);
        sortList.remove(Integer.valueOf(value));
    }

    public int top() {
        return stack.get(stack.size() - 1);
    }

    public int getMin() {
        return sortList.get(0);
    }

    /**
     * 方法二：
     * 时间复杂度：O(1)
     * 借助helper栈维护stack中同高度的最小值。
     */
    static class MinStack {

        private final List<Integer> stack;
        private final List<Integer> helper;

        public MinStack() {
            stack = new LinkedList<>();
            helper = new LinkedList<>();
        }

        public void push(int x) {
            stack.add(0, x);
            if (helper.size() > 0 && x > helper.get(0)) {
                // 如果x大于当前栈的最小值，那么加入x后最小值依然是上一次的最小值
                helper.add(0, helper.get(0));
            } else {
                helper.add(0, x);
            }
        }

        public void pop() {
            stack.remove(0);
            helper.remove(0);
        }

        public int top() {
            return stack.get(0);
        }

        public int getMin() {
            return helper.get(0);
        }
    }

    public static void main(String[] args) {
        LeetCode155 leetcode = new LeetCode155();
        leetcode.push(-2);
        leetcode.push(0);
        leetcode.push(-3);
        System.out.println(leetcode.getMin());
        leetcode.pop();
        System.out.println(leetcode.top());
        System.out.println(leetcode.getMin());


        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println(minStack.getMin());
        minStack.pop();
        System.out.println(minStack.top());
        System.out.println(minStack.getMin());
    }
}
